package LinkedList;

/**
 *  题目 ： 排序的循环链表
 *  题目简述 ：
 * 给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素insertVal ，使这个列表仍然是循环升序的。
 * 给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。
 * 如果有多个满足条件的插入位置，可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。
 * 如果列表为空（给定的节点是 null），需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。
 *
 */
public class OfferP29 {
    /**
     * 思路 ：
     * 即，有且仅仅在新插入的节点值在 两个节点的值之间的话，就可以插入；
     * 否则的话，只能插入到最大值和最小值之间
     * 特殊情况 ：
     * （1）循环链表中没有节点，即新插入的节点指向自己；
     * （2）循环链表中有且仅有一个节点，即节点之间相互指向；
     * @param head
     * @param insertVal
     * @return
     */
    public Node insert(Node head, int insertVal) {
        Node node = new Node(insertVal);
        // 特殊情况 ：循环链表中没有节点
        if(head == null){
            head = node;
            node.next = node;
        }
        // 由于其始终为 循环链表（特殊情况 ：循环链表中有且仅有一个节点）
        else if(head.next == head){
            head.next = node;
            node.next = head;
        }
        else {
            // 在循环链表中，插入节点
            insertNode(head , node);
        }
        return head;
    }

    private void insertNode(Node head, Node node) {
        /**
         * （1）若是在循环链表中，能够寻找到node在两个节点之间的，即可以直接插入；
         * （2）若是为寻找到，即在最大值节点和最小值节点中插入；
         */
        // 由于是有序的循环链表（值从小到大）
        Node cur = head;
        Node next = head.next;
        // 用来记录整个链表的最大值节点（由于当不能插入node节点时，必然会遍历整个循环链表，即必然会寻找到最大值节点）
        Node Big = head;
        // flag,是用来判断 是否能够使得node插入两个节点之间；
        Boolean flag = node.val >= cur.val && node.val < next.val;
        while(!flag && next != head){ // && 后面的 next != head，即为循环结束条件，当next指向head指针时，即整个循环链表已经循环一遍；
            // 循环链表中，所遍历的双节点右移；
            cur = next;
            next = next.next;
            if(cur.val > Big.val){
                Big = cur;
            }
            // 每次进循环，都需要对于flag的值进行更新
            flag = node.val >= cur.val && node.val <= next.val;
        }
        if(flag){
            // 若是flag为true的话，即可以在循环链表中进行node节点的插入；
            cur.next = node;
            node.next = next;
        }
        else {
            // 由于head不一定为循环链表中的最小节点；
            // 即，在flag为false的情况下，需要在最大节点值和最小节点值之间进行插入node节点；
            node.next = Big.next;
            Big.next = node;
        }
    }


    class Node {
        public int val;
        public Node next;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _next) {
            val = _val;
            next = _next;
        }
    };
}

